import java.util.HashMap;
import java.util.LinkedList;

public class LC662 {
    HashMap<Integer,Integer> leftIndex = new HashMap<>();
    HashMap<Integer,Integer> rightIndex = new HashMap<>();
    public int widthOfBinaryTree(TreeNode root) {
        int maxDepth=depthTree(root,0,0);
        int maxWidth = 0;
        for(int i=0;i<maxDepth;i++){
            int nowWidth = rightIndex.get(i)-leftIndex.get(i)+1;
            if(nowWidth>maxWidth){
                maxWidth=nowWidth;
            }
        }
        return maxWidth;
    }
    private int depthTree(TreeNode root,int rootIndex,int depth){
        int maxDepth = 1;
        if(leftIndex.getOrDefault(depth,Integer.MAX_VALUE)>rootIndex){
            leftIndex.put(depth,rootIndex);
        }
        if(rightIndex.getOrDefault(depth,Integer.MIN_VALUE)<rootIndex){
            rightIndex.put(depth,rootIndex);
        }
        if(root.left!=null){
            maxDepth=depthTree(root.left,rootIndex*2+1,depth+1);
        }
        if(root.right!=null){
            int temp=depthTree(root.right,rootIndex*2+2,depth+1);
            if(temp>maxDepth)
                return temp+1;
        }else {
            if(root.left==null){
                return 1;
            }
        }
        return maxDepth+1;
    }
}
